import networkx as nx
import matplotlib.pyplot as plt
import numpy as np
import random
import itertools
from itertools import *
from docplex.mp.model import Model
# from generate import GenerateNetwork
import copy
from functools import partial
import multiprocessing


node_num = 60
sd_num = 30
pro = 80
remaining_num = 6
β = 0.1



max_slot_num = 100
the_num = 10
# loop_num = 20
Reduction_factor = 10



class QNetwork: 
    def __init__(self, path_for_getxt, remaining_num_changing, node_num_changing):
        self.maxloop = []
        self.nodeList = []
        self.linkListProbability = []
        self.elMatrix = np.zeros((remaining_num_changing, node_num_changing))
        self.el_success = np.zeros((remaining_num_changing, node_num_changing))
        self.el_success_looping = np.zeros((remaining_num_changing, node_num_changing))
        self.ec_selectNodes = {}
        self.sdList = []
        self.sdList_all = []
        self.elWaste = 0
        self.remainingNumchanging = remaining_num_changing

        # self.window_size = 3
        try:
            self.readDataFromTxt(path_for_getxt)
        except:
            print("读取错误")

    class Link:
        def __init__(self, startNode, endNode, probability):
            self.startNode = startNode
            self.endNode = endNode
            self.probability = probability

    class Node:
        def __init__(self, nodeID):
            self.nodeID = nodeID
            self.adjacentNodes = []
            self.selectNodeID = 0
            self.epsFlag = 0

    def initSelectNodeID(self):
        # 24.1.13 23：43 可能要在这里对el_success做一个初始化，
        # el_success的同步更新，并初始化一个以loop为key的字典  
    # 更新每个eps节点的selectNodeID
        for node in self.nodeList:
            if node.epsFlag == 1:
                # 随机选择一个相邻节点的ID作为selectNodeID，或保持为0
                if node.adjacentNodes:
                    excluded_values = self.get_excluded_values(node.nodeID)
                    valid_nodes = [n for n in node.adjacentNodes if n not in excluded_values]
                    # print(valid_nodes)
                    if valid_nodes:
                        node.selectNodeID = random.choice(valid_nodes) 
                        print(f"eps {node.nodeID} selected neighbor {node.selectNodeID}")
                        self.el_success[self.remainingNumchanging-1][node.nodeID-1] = node.selectNodeID

    def updateSelectNodeID(self, el_success_before_loop):
    # 更新每个eps节点的selectNodeID
        sd_pair_step_num_grade_down = self.get_ep_step()

        # for ep_link in sd_pair_step_num_grade_down.keys():
        #     print("there is ep_link")
        #     for link_1 in ep_link:
        #         print(link_1.startNode, link_1.endNode)

        for node in self.nodeList:
            if node.epsFlag == 1:
                # print(f"循环到node{node.nodeID},这是一个eps")
                link = {}
                for neighbor in node.adjacentNodes:
                    for linkProbability in self.linkListProbability:
                        if linkProbability.startNode == node.nodeID and linkProbability.endNode == neighbor:
                            link[neighbor] = linkProbability         
                        elif linkProbability.startNode == neighbor and linkProbability.endNode == node.nodeID:
                            link[neighbor] = linkProbability
                ec_counter = {}
                excluded_values = self.get_excluded_values(node.nodeID)
                # print(f"已经得到node{node.nodeID}需要避开的neighbor：{excluded_values}")
                
                neighbor_pro = {}
                # 在这个对邻居节点的遍历过程中，需要在每一次尝试之后还原记录矩阵
                for neighbor in node.adjacentNodes:
                    self.el_success_looping = copy.deepcopy(el_success_before_loop)

                    if neighbor not in excluded_values:
                        
                        self.el_success_looping[self.remainingNumchanging-1][node.nodeID-1] = neighbor
                        ec_counter[neighbor] = self.calculateEcCount()

                        weight = len(sd_pair_step_num_grade_down)
                        for ep_links in sd_pair_step_num_grade_down.keys():
                            weight *= 1/Reduction_factor # 这一步很关键，修正了所有匹配到的第一个link权重都一样的问题
                            if link[neighbor] in ep_links:
                                ec_counter[neighbor] += weight

                        # neighbor_pro[neighbor] = self.getLinkProbability(node.nodeID, neighbor)
                        # neighbor_pro_grade_down = dict(sorted(neighbor_pro.items(), key=lambda item: item[1], reverse=False))
                        # weight_pro = len(neighbor_pro_grade_down)*Reduction_factor
                        # for neighbor_with_pro in neighbor_pro_grade_down.keys():
                        #     weight_pro *= 1/Reduction_factor
                        #     if neighbor == neighbor_with_pro:
                        #         ec_counter[neighbor] += weight_pro

                        # print(f"the weight is {weight} now")
                        # print(f"eps {node.nodeID} with neighbor {neighbor} has pf {ec_counter[neighbor]}")

                # print("已经进行了多轮迭代,还没有开始找最大值")

                #找到ec_counter[neighbor] 中值最大的键
                if ec_counter:
                    # max_value = max(ec_counter.values())
                    # max_elements = [key for key, value in ec_counter.items() if value == max_value]
                    # # 如果有多个具有最大值的元素，随机选择一个
                    # selected_node = random.choice(max_elements)
                    # node.selectNodeID = selected_node

                    node.selectNodeID = max(ec_counter, key = ec_counter.get)
                    # print(f"the selectnode is {node.selectNodeID} with the pf {ec_counter[node.selectNodeID]}")
                    self.el_success[self.remainingNumchanging-1][node.nodeID-1] = node.selectNodeID
                    self.ec_selectNodes[matrix_to_tuple(self.el_success)] = ec_counter[node.selectNodeID]
# 如何把矩阵作为键值对的key保存进字典

                # print(f"找到最大值对应的neighbor{node.selectNodeID},已经修改了self.el_success")





    def updateSelectNodeID_bytwo(self, el_success_before_loop):
    # 更新每两个eps节点的selectNodeID
        twobytwo_eps_nodes = self.get_twobytwo_eps_nodes()
        # 剪枝
        self.prune_bytwo(twobytwo_eps_nodes)
        sd_pair_step_num_grade_down = self.get_ep_step()

        # for ep_link in sd_pair_step_num_grade_down.keys():
        #     print("there is ep_link")
        #     for link_1 in ep_link:
        #         print(link_1.startNode, link_1.endNode)

        for two_node in twobytwo_eps_nodes:
            
            twobytwo_eps_neighbor_nodes = self.get_twobytwo_neighbor_nodes(two_node[0], two_node[1])

            links = {}
            ec_counter_bytwo = {}
            neighbor_pro = {}
            # print(f"the length of ec_counter_bytwo before valuing is {len(ec_counter_bytwo)}")

            for neighbor_bytwo in twobytwo_eps_neighbor_nodes:
                    
                for linkProbability in self.linkListProbability:
                    if ( linkProbability.startNode == two_node[0] and linkProbability.endNode == neighbor_bytwo[0] )\
                        or ( linkProbability.startNode == neighbor_bytwo[0] and linkProbability.endNode == two_node[0] ):
                        links[(two_node[0], neighbor_bytwo[0])] = linkProbability
                        links[(neighbor_bytwo[0], two_node[0])] = linkProbability
                    elif ( linkProbability.startNode == two_node[1] and linkProbability.endNode == neighbor_bytwo[1] )\
                        or ( linkProbability.startNode == neighbor_bytwo[1] and linkProbability.endNode == two_node[1] ):
                        links[(two_node[1], neighbor_bytwo[1])] = linkProbability
                        links[(neighbor_bytwo[1], two_node[1])] = linkProbability
                    
                # print(f"links已经加载完毕:{links.keys()}")

                self.el_success_looping = copy.deepcopy(el_success_before_loop)
                self.el_success_looping[self.remainingNumchanging-1][two_node[0]-1] = neighbor_bytwo[0]
                self.el_success_looping[self.remainingNumchanging-1][two_node[1]-1] = neighbor_bytwo[1]
                ec_counter_bytwo[neighbor_bytwo] = self.calculateEcCount()

                # print(f"the length of ec_counter_bytwo after valuing is {len(ec_counter_bytwo)}")

                weight = len(sd_pair_step_num_grade_down)
                for ep_links in sd_pair_step_num_grade_down.keys():
                    weight *= 1/Reduction_factor
                    if links[(two_node[0], neighbor_bytwo[0])] in ep_links \
                        or links[(two_node[1], neighbor_bytwo[1])] in ep_links :
                            # or links[(neighbor_bytwo[0], two_node[0])] in ep_links \
                            #     or links[(neighbor_bytwo[1], two_node[1])] in ep_links :
                        ec_counter_bytwo[neighbor_bytwo] += weight
                # print("已经完成了pf值的修改")
                        

                # neighbor_pro[neighbor_bytwo] = self.getLinkProbability(self.getNode(two_node[0]).nodeID, neighbor_bytwo[0]) + \
                #                                     self.getLinkProbability(self.getNode(two_node[1]).nodeID, neighbor_bytwo[1])
                # neighbor_pro_grade_down = dict(sorted(neighbor_pro.items(), key=lambda item: item[1], reverse=False))
                # weight_pro = len(neighbor_pro_grade_down)*Reduction_factor
                # for neighbor_with_pro in neighbor_pro_grade_down.keys():
                #     weight_pro *= 1/Reduction_factor
                #     if neighbor_bytwo[0] == neighbor_with_pro or neighbor_bytwo[1] == neighbor_with_pro:
                #         ec_counter_bytwo[neighbor_bytwo] += weight_pro                
            
            # if not ec_counter_bytwo:
                # print(f"the two nodes are {two_node[0]} with neighbors ({self.getNode(two_node[0]).adjacentNodes}),{two_node[1]} with neighbors ({self.getNode(two_node[1]).adjacentNodes}) ")
                
            if ec_counter_bytwo:
                self.getNode(two_node[0]).selectNodeID = max(ec_counter_bytwo, key = ec_counter_bytwo.get)[0]
                self.getNode(two_node[1]).selectNodeID = max(ec_counter_bytwo, key = ec_counter_bytwo.get)[1]
                self.el_success[self.remainingNumchanging-1][two_node[0]-1] = self.getNode(two_node[0]).selectNodeID
                self.el_success[self.remainingNumchanging-1][two_node[1]-1] = self.getNode(two_node[1]).selectNodeID
                self.ec_selectNodes[matrix_to_tuple(self.el_success)] = ec_counter_bytwo[(self.getNode(two_node[0]).selectNodeID, self.getNode(two_node[1]).selectNodeID)]
                # print("mark")      
            
        # 2024/1/13 19:40写到这里，需要想一个排除已存在el的neighbor节点组合的方法，并且以组合为单位更新selectNodeID
                
        # 2024/1/12 17:00写到这里
        #     2024/1/13 12:00写到这里(双节点剪枝部分已经写完)

    def BestResponse(self, ep_links_of_sd_pair_11_18 = []):

        # print("before init")
        # for node in self.nodeList:
        #     print(node.selectNodeID)

        self.el_success = copy.deepcopy(self.elMatrix)    
        # self.initSelectNodeID()

        # print("after init")
        # for node in self.nodeList:
        #     print(node.selectNodeID)


        

        # print("before updating")
        # print(self.el_success)
        # print(self.elMatrix)

        # for loop in range(self.maxloop[0]):
        for loop in range(4):
            el_success_before_loop = copy.deepcopy(self.el_success) 
            self.updateSelectNodeID(el_success_before_loop) 
            # print(f"完成第{loop+1}次循环")
            
            #添加判断el_success是否不再变化的语句 
            if np.array_equal(el_success_before_loop, self.el_success):
                # print(f"已经在单节点迭代中收敛，轮数为{loop+1}")
                nodes_selected = compare_and_retain_differences(self.elMatrix, self.el_success)
                # print(f"nodes_selected:{nodes_selected}")
                eps_selectNode = get_eps_selectNode(nodes_selected)
                # print("这一轮中的节点选择情况为：", eps_selectNode)

                # print("update之前的elMatrix", self.elMatrix)
                # 概率更新el，检查是否新建成ec，更新el表和sd对表，滑动el矩阵
                self.update_elMatrix(eps_selectNode)
                # print("检查ec并清空el之前", self.elMatrix)
                # print(len(self.sdList))
                self.check_if_ec_and_update(ep_links_of_sd_pair_11_18)
                # print("滑动前", self.elMatrix)
                self.elMatrix = sliding_matrix(self.elMatrix)
                # print("滑动之后", self.elMatrix)
                # 需要记录这一个时隙达到博弈收敛用掉的轮数 24.1.23
                # 修改一下循环的方式, 这里的loop还没有派上用场
                return loop + 1
        # print("单节点循环结束,没有收敛")
        for loop in range(8):
            el_success_before_loop = copy.deepcopy(self.el_success)
            self.updateSelectNodeID_bytwo(el_success_before_loop)
            #添加判断el_success是否不再变化的语句
            if np.array_equal(el_success_before_loop, self.el_success):
                # print(f"已经在双节点迭代中收敛，轮数为{loop+1}")
                nodes_selected = compare_and_retain_differences(self.elMatrix, self.el_success)
                eps_selectNode = get_eps_selectNode(nodes_selected)
                # print("这一轮中的节点选择情况为：", eps_selectNode) 
                # 概率更新el，检查是否新建成ec，更新
                # el表和sd对表，滑动el矩阵
                self.update_elMatrix(eps_selectNode)
                self.check_if_ec_and_update()
                self.elMatrix = sliding_matrix(self.elMatrix)
                # 需要记录这一个时隙达到博弈收敛用掉的轮数 24.1.23
                # 修改一下循环的方式, 这里的loop还没有派上用场
                return loop + 4
        # print("经过单节点迭代和双节点迭代都没有收敛")
        example_matrix = self.elMatrix
        ec_selectNodes = self.ec_selectNodes
        # print("max(ec_selectNodes, key=ec_selectNodes.get):",max(ec_selectNodes, key=ec_selectNodes.get))
        el_success_with_max = tuple_to_matrix(max(ec_selectNodes, key=ec_selectNodes.get))
        # print("el_success_with_max",el_success_with_max)
        # el_success_with_max = max(ec_selectNodes, key = ec_selectNodes.get)
        nodes_selected = compare_and_retain_differences(self.elMatrix, el_success_with_max)
        # print("nodes_selected",nodes_selected)
        eps_selectNode = get_eps_selectNode(nodes_selected)
        # print("这一轮中的节点选择情况为：", eps_selectNode)       
        # 概率更新el，检查是否新建成ec，更新el表和sd对表，滑动el矩阵
        # print("1111111")
        self.update_elMatrix(eps_selectNode)
        # print("2222222")
        self.check_if_ec_and_update()
        # print("3333333")
        self.elMatrix = sliding_matrix(self.elMatrix)
        # print("4444444")
        # 需要记录这一个时隙达到博弈收敛用掉的轮数 24.1.23
        # 修改一下循环的方式, 这里的loop还没有派上用场
        return 5

    # 通信开销统计函数还有待修改,需要和每个时隙的迭代次数结合起来    
    def communication_cost(self, traffic, loop):
        communication_cost_overall = 0 
        communication_cost_of_links = {}
        # 计算eps节点两两之间的最短跳数*（对应的数据大小）
        twobytwo_eps_nodes = self.get_twobytwo_eps_nodes()
        for two_node in twobytwo_eps_nodes:
            step = len(self.getShortedPath(two_node[0], two_node[1])) 
            degree1 = len(two_node[0].adjacentNodes)
            degree2 = len(two_node[1].adjacentNodes)
            communication_cost_overall += step * (degree1 * traffic[0] + loop * traffic[1] + degree2 * traffic[0] + loop * traffic[1])
        # 统计单link负载，如果某个link出现在某个eps对之间的路径上，
        # 就加一个该eps对的两个节点分别的（每个eps的度数*（linkID：el可持续时隙数）+ （epsNodeID：selectNodeID）），
        # 然后得到所有link中这个值最大的link，以及对应的该值    
            for link in self.linkListProbability:
                communication_cost_of_links[link] = 0
                eps_path_links = self.get_path_links_of_eps_pair(two_node[0], two_node[1])
                if link in eps_path_links:
                    degree1 = len(two_node[0].adjacentNodes)
                    degree2 = len(two_node[1].adjacentNodes)
                    communication_cost_of_links[link] += (degree1 * traffic[0] + loop * traffic[1] + degree2 * traffic[0] + loop * traffic[1])
        max_link, max_traffic = max(communication_cost_of_links.items(), key=lambda x: x[1])

        return communication_cost_overall, communication_cost_of_links, max_link, max_traffic

    def Pro_first(self):
        for node in self.nodeList:
            if node.epsFlag == 1:
                neighbor_pro = {}
                if node.adjacentNodes:
                    for neighbor in node.adjacentNodes:
                        excluded_values = self.get_excluded_values(node.nodeID)
                        if neighbor not in excluded_values:
                            neighbor_pro[neighbor] = self.getLinkProbability(node.nodeID, neighbor)
                #找到neighbor_pro[] 中值最大的键
                if neighbor_pro:
                    max_value = max(neighbor_pro.values())
                    max_elements = [key for key, value in neighbor_pro.items() if value == max_value]
                    # 如果有多个具有最大值的元素，随机选择一个
                    selected_node = random.choice(max_elements)
                    # print("最大值的个数", len(max_elements))
                    node.selectNodeID = selected_node
                # 更新elMatrix
                for index in range(self.elMatrix.shape[1]):
                    if index+1 == node.nodeID:
                        choices_array = np.array([node.selectNodeID, 0])
                        # 获取概率值 v
                        v = self.getLinkProbability(node.nodeID, neighbor)
                        self.elMatrix[self.remainingNumchanging-1][index] = np.random.choice(choices_array, p=[v, 1-v])
        # print("profirst 执行中")
        self.check_if_ec_and_update()
        # print("滑动前", self.elMatrix)
        self.elMatrix = sliding_matrix(self.elMatrix)
        # print("滑动之后", self.elMatrix)

    def Step_first(self):
        sd_pair_step_num = {}
        for sd_pair in self.sdList:
            # EP = self.getShortedPath_EPS(sd_pair[0], sd_pair[1])
            ep_links_of_sd = self.get_ep_links_of_sd_pair(sd_pair[0], sd_pair[1])
            el_links = self.get_el_links_elMatrix()
            unique_elements_a = set(ep_links_of_sd)
            unique_elements_b = set(el_links)
            elements_not_in_b = [x for x in unique_elements_a if x not in unique_elements_b]
            # # 计算不存在的元素个数
            # Step_num = len(elements_not_in_b)
            # sd_pair_step_num[tuple(ep_links_of_sd)] = Step_num
            # sd_pair_step_num_grade_down = dict(sorted(sd_pair_step_num.items(), key=lambda item: item[1], reverse=False))
        ### 修改版，遇到多个step_num值相同的键值对时，将他们随机排序而不是按照固定的顺序排列
            Step_num = len(elements_not_in_b)
            sd_pair_step_num[tuple(ep_links_of_sd)] = Step_num
            # 将具有相同值的键值对分组
            grouped_items = {}
            for key, value in sd_pair_step_num.items():
                grouped_items.setdefault(value, []).append((key, value))
            # 对每个值相同的组进行随机排序
            for key, items in grouped_items.items():
                random.shuffle(items)
            # 将随机排序后的键值对重新组合成字典
            sd_pair_step_num_grade_down = dict(item for sublist in grouped_items.values() for item in sublist)            
        
        for node in self.nodeList:
            if node.epsFlag == 1:
                link = {}
                for neighbor in node.adjacentNodes:
                    for linkProbability in self.linkListProbability:
                        if linkProbability.startNode == node.nodeID and linkProbability.endNode == neighbor:
                            link[neighbor] = linkProbability
                        elif linkProbability.startNode == neighbor and linkProbability.endNode == node.nodeID:
                            link[neighbor] = linkProbability
                    # if neighbor not in link:
                    #     link[neighbor] = []
                exit_loop = False
                for ep_link in sd_pair_step_num_grade_down.keys():
                    for neighbor in node.adjacentNodes:
                        if neighbor not in self.get_excluded_values(node.nodeID):
                            if link[neighbor] in ep_link:
                                # print("有link在ep中")
                                node.selectNodeID = neighbor
                                exit_loop = True    
                                break
                    if exit_loop:
                        # print("exiting")
                        break
        # 更新elMatrix
        for node in self.nodeList:
            if node.epsFlag == 1:
                for index in range(self.elMatrix.shape[1]):
                    # if node.selectNodeID == 0:
                    #     print("node.selectNodeID is 0")
                    if index+1 == node.nodeID:
                        # if node.selectNodeID == 0:
                        #     print("node.selectNodeID is 0")
                        choices_array = np.array([node.selectNodeID, 0])
                        # 获取概率值 v
                        v = self.getLinkProbability(node.nodeID, node.selectNodeID)*0.8
                        # if v > 1 or v < 0: 
                        #     print(f"link{(node.nodeID, node.selectNodeID)}的el建成概率为{v}")
                        # else:
                        #     self.elMatrix[self.remainingNumchanging-1][index] = np.random.choice(choices_array, p=[v, 1-v])
                        self.elMatrix[self.remainingNumchanging-1][index] = np.random.choice(choices_array, p=[v, 1-v])
        self.check_if_ec_and_update()
        self.elMatrix = sliding_matrix(self.elMatrix)
                        
    def Remainning_first(self, sd_pair_urgency):
        elMatrix = self.elMatrix
        el_nodes = {}
        for row in elMatrix:
            # print(row, "/n")
            index = 0 
            for element in row:
                index += 1
                if element != 0:
                    # print(f"there is an element: {(index, element)}")
                    row_tuple = tuple(row)
                    if row_tuple not in el_nodes:
                        el_nodes[row_tuple] = []  # 如果该行不存在于 el_nodes 字典中，则创建一个空列表
                    el_nodes[row_tuple].append((index, element))

        # print(len(el_nodes))
        # print("el_nodes is", el_nodes)
        el_links = {}
        for linkProbability in self.linkListProbability:
            for row, nodes in el_nodes.items():
                if row not in el_links:
                    el_links[row] = []  # 初始化列表
                for link_nodes in nodes:
                    if (linkProbability.startNode == link_nodes[0] and linkProbability.endNode == link_nodes[1]) or \
                    (linkProbability.startNode == link_nodes[1] and linkProbability.endNode == link_nodes[0]):
                        el_links[row].append(linkProbability)

        # print(len(el_links))
        # print("el_links is", el_links)
        sd_pair_urgency = {}    
        for sd_pair in self.sdList:
            ep_links_of_sd = self.get_ep_links_of_sd_pair(sd_pair[0], sd_pair[1])
            if tuple(ep_links_of_sd) not in sd_pair_urgency:
                sd_pair_urgency[tuple(ep_links_of_sd)] = 0
            for row in el_links.keys():
                weight = 4
                for link in el_links[row]:
                    # print("ininininini")
                    if link in ep_links_of_sd:
                        sd_pair_urgency[tuple(ep_links_of_sd)] += weight 
                weight -= 1
    
        #         if tuple(ep_links_of_sd) in sd_pair_urgency:
        #             print(f"sd_pair {sd_pair} is put in")
        #             print(f"sd_pair_urgency[{ep_links_of_sd}] is {sd_pair_urgency[tuple(ep_links_of_sd)]}")
        # print("sd_pair_urgency is", sd_pair_urgency)
        # print("length of sd_pair_urgency is", len(sd_pair_urgency))
        # print("length of sd_pair_list is", len(self.sdList))

        sd_pair_urgency_grade_down = dict(sorted(sd_pair_urgency.items(), key=lambda item: item[1], reverse=False))


    # ### 修改版，遇到多个weight值相同的键值对时，将他们随机排序而不是按照固定的顺序排列
    #     # 将具有相同值的键值对分组
    #     grouped_items = {}
    #     for key, value in sd_pair_urgency.items():
    #         grouped_items.setdefault(value, []).append((key, value))
    #     # 对每个值相同的组进行随机排序
    #     for key, items in grouped_items.items():
    #         random.shuffle(items)
    #     # 将随机排序后的键值对重新组合成字典
    #     sd_pair_urgency_grade_down = dict(item for sublist in grouped_items.values() for item in sublist)    


        # print(sd_pair_urgency_grade_down)
        for node in self.nodeList:
            if node.epsFlag == 1:
                # print(f"{node.nodeID} with epsflag = 1")
                link = {}
                for neighbor in node.adjacentNodes:
                    for linkProbability in self.linkListProbability:
                        if linkProbability.startNode == node.nodeID and linkProbability.endNode == neighbor:
                            link[neighbor] = linkProbability
                        elif linkProbability.startNode == neighbor and linkProbability.endNode == node.nodeID:
                            link[neighbor] = linkProbability
                # for link_neighbor in link:
                #     print(link_neighbor)
                exit_loop = False
                for ep_link in sd_pair_urgency_grade_down.keys():
                    # print("ep_link is ", ep_link)
                    for neighbor in node.adjacentNodes:
                        # print("neighbor's link is", link[neighbor])
                        if neighbor not in self.get_excluded_values(node.nodeID):
                            if link[neighbor] in ep_link:
                                # print("in~~~~~~~~")
                                node.selectNodeID = neighbor
                                # print(neighbor)
                                # print(f"{node.nodeID}的selectnodeid是{node.selectNodeID}")
                                exit_loop = True    
                                break
                    if exit_loop:
                        # print("exiting")
                        break
                    # else:
                    #     node.selectNodeID = random.choice(node.adjacentNodes)
                    #     print(f"{node.nodeID}的selectnodeid随机为{node.selectNodeID}")
                        # 问题在这里，好像随机出来的结果有一些不在adjacentNodes的范围里

                        # 貌似随机出来的结果虽然是从adjacentNodes里面来的，但是没有一个在ep_link里面的，导致没有break

        # 更新elMatrix
        for node in self.nodeList:
            if node.epsFlag == 1:
                # print(f"node{node.nodeID}的seletnodeid是{node.selectNodeID}")
                for index in range(self.elMatrix.shape[1]):
                        if index+1 == node.nodeID:
                            choices_array = np.array([node.selectNodeID, 0])
                            # 获取概率值 v
                            v = self.getLinkProbability(node.nodeID, node.selectNodeID)
                            # if v > 1 or v < 0: 
                            #     print(f"link{(node.nodeID, node.selectNodeID)}的el建成概率为{v}")
                            # else:
                                # print(f"link{(node.nodeID, node.selectNodeID)}的el将以{v}的概率成功建成")
                                # self.elMatrix[self.remainingNumchanging-1][index] = np.random.choice(choices_array, p=[v, 1-v])
                            # print(f"link{(node.nodeID, node.selectNodeID)}的el将以{v}的概率成功建成")
                            # else:
                            self.elMatrix[self.remainingNumchanging-1][index] = np.random.choice(choices_array, p=[v, 1-v])
        # print("sd_pair_urgency_grade_down的长度：", len(sd_pair_urgency_grade_down))
        # print(sd_pair_urgency_grade_down)
        
        # print("sd对的数量：", len(self.sdList))
        # if len(self.sdList) == len(sd_pair_urgency):
        #     print("长度匹配：")
        # else:
        #     print("长度不匹配")
        # print("Length of self.sdList:", len(self.sdList))
        # print("Length of sd_pair_urgency:", len(sd_pair_urgency))
        # if len(sd_pair_urgency_grade_down) == len(sd_pair_urgency):
        #     print("排序没有改变元素数量")
        # else:
        #     print("排序改变了元素数量")


        self.check_if_ec_and_update()

        self.elMatrix = sliding_matrix(self.elMatrix)

    def get_twobytwo_eps_nodes(self):
        nodelist = self.nodeList
        eps_nodes = []
        for node in nodelist:
            if node.epsFlag == 1:
                eps_nodes.append(node.nodeID)
        twobytwo_eps_nodes = []
        twobytwo_eps_nodes = list(itertools.permutations(eps_nodes, 2))
        return twobytwo_eps_nodes

    def get_twobytwo_neighbor_nodes(self, eps_1, eps_2):
        # 注意，这里的eps_1, eps_2是node对象，不是id，不是数字
        twobytwo_eps_neighbor_nodes = []
        eps_1_neighbor = []
        for node in self.getNode(eps_1).adjacentNodes:
            if node not in self.get_excluded_values(eps_1):
                eps_1_neighbor.append(node)
        eps_2_neighbor = []
        for node in self.getNode(eps_2).adjacentNodes:
            if node not in self.get_excluded_values(eps_2):
                eps_2_neighbor.append(node)
        # 经过修改，这里获得的是一个已经提纯过的邻居节点组合了 24.1.13 19：48                       
        twobytwo_eps_neighbor_nodes = product(eps_1_neighbor, eps_2_neighbor)
        return twobytwo_eps_neighbor_nodes
    
    def prune_bytwo(self, twobytwo_eps_nodes):
        for two_node in twobytwo_eps_nodes:
            if len(self.getShortedPath(two_node[0], two_node[1])) > 4:
                del two_node
    
    # 检查是否有ec建成，以更新elMatrix（删除已经建成了的ec所包括的el），并从sdList里面删除对应的sd对
    def check_if_ec_and_update(self, ep_links_of_sd_pair_11_18 = []):
        for sd_pair in self.sdList:
            # 检查sd_pair的ep上的所有link是否都存在el，如果是，则更新elMatrix
            ep_links_of_sd = self.get_ep_links_of_sd_pair(sd_pair[0], sd_pair[1])

            # if not ep_links_of_sd:
            #     # print("有sd对之间的路径为空,", sd_pair)
            #     # print(self.getShortedPath_EPS(sd_pair[0], sd_pair[1]))
            #     if sd_pair == [11, 18]:
            #         # ep_links_of_sd = self.get_ep_links_of_sd_pair(11, 18)

            #         ep_links_of_sd = ep_links_of_sd_pair_11_18
                    # print("hhhh")
                # [<network.QNetwork.Link object at 0x7fde4c0db610>, <network.QNetwork.Link object at 0x7fde4c0db670>, <network.QNetwork.Link object at 0x7fde4c0dbc10>, <network.QNetwork.Link object at 0x7fde4c0dd130>]
            
            # print(ep_links_of_sd)
            el_links = self.get_el_links_elMatrix()

            # if el_links:
            #     print("存在不为空的el状态矩阵")
            # print("el_links", el_links)

            # if all(el_links for link in ep_links_of_sd):
            set_a = set(el_links)
            set_b = set(ep_links_of_sd)
            # print("set_a", set_a)
            # print("set_b", set_b)

            if set_b.issubset(set_a):
                # print("b is subset")

                # print(f"sd对{sd_pair}, 路径{self.getShortedPath_EPS(sd_pair[0], sd_pair[1])}")
                # print(self.elMatrix)
                # for link in el_links:
                    # print("el_link", (link.startNode, link.endNode))
                # for link in ep_links_of_sd:
                    # print("ep_link", (link.startNode, link.endNode))
                # sd_ec_count = 1
                for link in ep_links_of_sd:
                    # 先把link对应到elMatrix上，将值置为0
                    startNode = link.startNode
                    endNode = link.endNode  
                    for row_index in range(self.elMatrix.shape[0]):
                        for column_index in range(self.elMatrix.shape[1]):
                            if self.elMatrix[row_index][column_index] == startNode and column_index + 1 == endNode:
                                self.elMatrix[row_index][column_index] = 0
                            elif self.elMatrix[row_index][column_index] == endNode and column_index + 1 == startNode:
                                self.elMatrix[row_index][column_index] = 0
                # print(self.elMatrix)
                # 将该sd对从列表中删除
                self.sdList.remove(sd_pair)   
        # 增加检查还未被利用的即将失效的el
        for elment in self.elMatrix[0]:
            if elment != 0:
                self.elWaste += 1


    def get_ep_step(self):
        sd_pair_step_num = {}
        for sd_pair in self.sdList:
            # EP = self.getShortedPath_EPS(sd_pair[0], sd_pair[1])
            ep_links_of_sd = self.get_ep_links_of_sd_pair(sd_pair[0], sd_pair[1])
            el_links = self.get_el_links_elMatrix()
            unique_elements_a = set(ep_links_of_sd)
            unique_elements_b = set(el_links)
            elements_not_in_b = [x for x in unique_elements_a if x not in unique_elements_b]
            # 计算不存在的元素个数
            Step_num = len(elements_not_in_b)
            sd_pair_step_num[tuple(ep_links_of_sd)] = Step_num
            sd_pair_step_num_grade_down = dict(sorted(sd_pair_step_num.items(), key=lambda item: item[1], reverse=False))
        return sd_pair_step_num_grade_down

    def calculateEcCount(self):
        ec_count = 0
        for sd_pair in self.sdList:   
            # 检查sd_pair的ep上的所有link是否都存在el，如果是，则计算并统计ec建成期望
            ep_links_of_sd = self.get_ep_links_of_sd_pair(sd_pair[0], sd_pair[1])
            el_links = self.get_el_links()

            set_a = set(el_links)
            set_b = set(ep_links_of_sd)
            if set_b.issubset(set_a):
            # if all(el_links for link in ep_links_of_sd):
                sd_ec_count = 1
                for link in ep_links_of_sd:
                    sd_ec_count *= link.probability
                ec_count += sd_ec_count
        
        return ec_count

    def get_el_links(self):
        el_success_looping = self.el_success_looping
        el_nodes = []
        for row in el_success_looping:
            index = 0
            for element in row:
                index += 1
                if element != 0:
                    el_nodes.append((index, element))
        el_links = []
        #  这里的取link函数写的可能有问题，有待检查
        for linkProbability in self.linkListProbability:
            for link_nodes in el_nodes:
                if linkProbability.startNode == link_nodes[0] and linkProbability.endNode == link_nodes[1]:
                    el_links.append(linkProbability)
                elif linkProbability.startNode == link_nodes[1] and linkProbability.endNode == link_nodes[0]:
                    el_links.append(linkProbability)
        return el_links
    
    def calculateEcCount_mlp(self, el_success_looping_neighbor):
        ec_count = 0
        for sd_pair in self.sdList:
            # 检查sd_pair的ep上的所有link是否都存在el，如果是，则计算并统计ec建成期望
            ep_links_of_sd = self.get_ep_links_of_sd_pair(sd_pair[0], sd_pair[1])
            el_links = self.get_el_links_mlp(el_success_looping_neighbor)

            set_a = set(el_links)
            set_b = set(ep_links_of_sd)
            if set_b.issubset(set_a):
            # if all(el_links for link in ep_links_of_sd):
                sd_ec_count = 1
                for link in ep_links_of_sd:
                    sd_ec_count *= link.probability
                ec_count += sd_ec_count
        return ec_count

    def get_el_links_mlp(self, el_success_looping_neighbor):
        el_success_looping = el_success_looping_neighbor
        el_nodes = []
        for row in el_success_looping:
            index = 0
            for element in row:
                index += 1
                if element != 0:
                    el_nodes.append((index, element))
        el_links = []
        #  这里的取link函数写的可能有问题，有待检查
        for linkProbability in self.linkListProbability:
            for link_nodes in el_nodes:
                if linkProbability.startNode == link_nodes[0] and linkProbability.endNode == link_nodes[1]:
                    el_links.append(linkProbability)
                elif linkProbability.startNode == link_nodes[1] and linkProbability.endNode == link_nodes[0]:
                    el_links.append(linkProbability)
        return el_links

    def get_el_links_elMatrix(self):
        elMatrix = self.elMatrix
        el_nodes = []
        for row in elMatrix:
            index = 0
            for element in row:
                index += 1
                if element != 0:
                    el_nodes.append((index, element))
        el_links = []
        # print("el_links", el_links)
        #  这里的取link函数写的可能有问题，有待检查
        # 24.1.24 这里的方法应该没有问题,可以正常调用startNode
        for linkProbability in self.linkListProbability:
            for link_nodes in el_nodes:
                if linkProbability.startNode == link_nodes[0] and linkProbability.endNode == link_nodes[1]:
                    el_links.append(linkProbability)
                elif linkProbability.startNode == link_nodes[1] and linkProbability.endNode == link_nodes[0]:
                    el_links.append(linkProbability)
        return el_links

    def get_ep_links_of_sd_pair(self , sourceID, destinationID):
        EP = self.getShortedPath_EPS(sourceID, destinationID)
        if not EP:
            print("存在路径为空的sd对")
        ep_links = []
        # 问题出在这里，
        for linkProbability in self.linkListProbability:
            for index in range(len(EP)-1):
                if linkProbability.startNode == EP[index] and linkProbability.endNode == EP[index+1]:
                    ep_links.append(linkProbability)
                elif linkProbability.startNode == EP[index+1] and linkProbability.endNode == EP[index]:
                    ep_links.append(linkProbability)
        return ep_links

    def update_elMatrix(self, eps_selectNode):
            for index in range(self.elMatrix.shape[1]):
                for key, value in eps_selectNode.items():
                    if self.getNode(key).epsFlag == 1:
                            
                        if index+1 == key:
                            # print(key, value[0])
                            # 将 [value, 0] 转换为 NumPy 数组
                            choices_array = np.array([self.getNode(key).selectNodeID, 0])
                            # 获取概率值 v
                            v = self.getLinkProbability(key, self.getNode(key).selectNodeID)
                            # print("link上的概率(原版本)：", v)
                            # print("link上的概率(int版本)：", int(v))
                            # 使用 np.random.choice() 来进行随机选择
                            if v > 0 :
                                self.elMatrix[self.remainingNumchanging-1][index] = np.random.choice(choices_array, p=[v, 1-v])
                            else:
                                print(key,value[0], v)
                            # if row[index] != 0:
                            #     print("有el被成功创建了")

    def get_excluded_values(self, value):
        excluded_values = []
        matrix = self.elMatrix
        for row in matrix:
            element = row[value-1] 
            if element != 0:
                excluded_values.append(element)
            # 这里添加检索是否被其他eps选择的代码
            for index in range(matrix.shape[1]):
                if row[index] == value:
                    excluded_values.append(index+1)
        return excluded_values

    def getShortedPath_EPS(self, startNodeID, endNodeID):
        # 创建一个字典来保存节点的距离和路径
        distances = {}
        paths = {}
        visited = set()
        # 初始化距离为无穷大，路径为空列表
        for node in self.nodeList:
            distances[node.nodeID] = float('inf')
            paths[node.nodeID] = []
        # 将起始节点的距离设置为0
        distances[startNodeID] = 0
        while len(visited) < len(self.nodeList):
            # 找到未访问节点中距离最小的节点
            min_distance = float('inf')
            min_node = None
            for node in self.nodeList:
                if node.nodeID not in visited and distances[node.nodeID] < min_distance:
                    min_distance = distances[node.nodeID]
                    min_node = node
            if min_node is None:
                # 没有找到可到达的节点
                break
            # 标记节点为已访问
            visited.add(min_node.nodeID)
            # 更新相邻节点的距离和路径
            for neighborID in min_node.adjacentNodes:
                neighbor = self.getNode(neighborID)
                # 检查当前节点和相邻节点的类型
                is_current_eps = min_node.epsFlag == 1
                is_neighbor_eps = neighbor.epsFlag == 1
                if is_current_eps or is_neighbor_eps:
                    # 计算新的距离
                    new_distance = distances[min_node.nodeID] + 1
                    if new_distance < distances[neighbor.nodeID]:
                        # 更新距离和路径
                        distances[neighbor.nodeID] = new_distance
                        paths[neighbor.nodeID] = paths[min_node.nodeID] + \
                            [neighbor.nodeID]
        paths[endNodeID].insert(0, startNodeID)
        return paths[endNodeID]


  
    
    def getShortedPath(self, startNodeID, endNodeID):
        # 创建一个字典来保存节点的距离和路径
        distances = {}
        paths = {}
        visited = set()
        # 初始化距离为无穷大，路径为空列表
        for node in self.nodeList:
            distances[node.nodeID] = float('inf')
            paths[node.nodeID] = []
        # 将起始节点的距离设置为0
        distances[startNodeID] = 0
        while len(visited) < len(self.nodeList):
            # 找到未访问节点中距离最小的节点
            min_distance = float('inf')
            min_node = None
            for node in self.nodeList:
                if node.nodeID not in visited and distances[node.nodeID] < min_distance:
                    min_distance = distances[node.nodeID]
                    min_node = node
            if min_node is None:
                # 没有找到可到达的节点
                break
            # 标记节点为已访问
            visited.add(min_node.nodeID)
            # 更新相邻节点的距离和路径
            for neighborID in min_node.adjacentNodes:
                neighbor = self.getNode(neighborID)             
                # 计算新的距离
                new_distance = distances[min_node.nodeID] + 1
                if new_distance < distances[neighbor.nodeID]:
                    # 更新距离和路径
                    distances[neighbor.nodeID] = new_distance
                    paths[neighbor.nodeID] = paths[min_node.nodeID] + \
                        [neighbor.nodeID]
        paths[endNodeID].insert(0, startNodeID)            
        return paths[endNodeID]

    def showNetwork(self):
        with open('./data/generate.txt', 'r') as file:
            lines = file.readlines()
        n = int(lines[0])
        nodes = [int(line) for line in lines[1:n+1]]
        G = nx.Graph()
        G.add_nodes_from(nodes)
        m = int(lines[n+1])
        for line in lines[n+2:]:
            start, end, weight = map(int, line.split())
            G.add_edge(start, end, weight=weight)
        fig, ax = plt.subplots()
        pos = nx.spring_layout(G, seed=41)
        nx.draw(G, pos, ax=ax, with_labels=True, node_color='red',
                node_size=300, font_size=8, alpha=1)
        edge_labels = nx.get_edge_attributes(G, 'weight')
        nx.draw_networkx_edge_labels(
            G, pos, edge_labels=edge_labels, font_size=6)
        plt.title("Network Topology")
        plt.show()

    def getLinkProbability(self, startID, endID):
        for linkProbability in self.linkListProbability:
            if linkProbability.startNode == startID and linkProbability.endNode == endID:
                return linkProbability.probability
            if linkProbability.startNode == endID and linkProbability.endNode == startID:
                return linkProbability.probability
        return -1

    def getNode(self, nodeId):
        if nodeId - 1 >= len(self.nodeList) or nodeId - 1 < 0:
            return self.Node(-1)
        return self.nodeList[nodeId - 1]

    def readDataFromTxt(self, path):
        with open(path, 'r') as file:
            lines = file.readlines()
            numNodes = int(lines[0])
            nodeIDs = [int(line.strip()) for line in lines[1: numNodes + 1]]
            for nodeID in nodeIDs:
                self.nodeList.append(self.Node(nodeID))
            numLinks = int(lines[numNodes + 1])
            for i in range(numNodes + 2, numNodes + numLinks + 2):
                linkData = lines[i].split()
                startNode = int(linkData[0])
                endNode = int(linkData[1])
                self.nodeList[startNode - 1].adjacentNodes.append(endNode)
                self.nodeList[endNode - 1].adjacentNodes.append(startNode)
                probability = int(linkData[2])/100
                linkProbability = self.Link(
                    startNode, endNode, probability)
                self.linkListProbability.append(linkProbability)
            sdNum = int(lines[numNodes + numLinks + 2])
            self.sdList = []
            for i in range(numNodes + numLinks + 3, numNodes + numLinks + sdNum + 3):
                sdData = lines[i].split()
                self.sdList.append([int(sdData[0]), int(sdData[1])])
                self.sdList_all.append([int(sdData[0]), int(sdData[1])])
            epsNodeNum = int(lines[numNodes + numLinks + sdNum + 3])
            for i in range(numNodes + numLinks + sdNum + 4, numNodes + numLinks + epsNodeNum + sdNum + 4):
                epsNodeID = int(lines[i])
                self.getNode(epsNodeID).epsFlag = 1
            # # 添加了不同迭代单位的最大迭代次数 的值
            # maxloopNum = int(lines[numNodes + numLinks + sdNum + epsNodeNum + 4])
            # self.maxloop = []
            # for i in range(numNodes + numLinks + sdNum + epsNodeNum +5, numNodes + numLinks + sdNum + epsNodeNum + maxloopNum + 5):
            #     self.maxloop.append(i)         
                
    # 新增数据结构：      self.nodeList      eps_ep_list
    def get_epList(self):
        epList = {}
        index_of_ep = 1
        for sd_pair in self.sdList:
            # 检查sd_pair的ep上的所有link是否都存在el，如果是，则更新elMatrix
            epList[index_of_ep] = self.getShortedPath_EPS(sd_pair[0], sd_pair[1])
            index_of_ep += 1
        return epList
    
    def get_eps_ep_list(self, epList):
        eps_ep = {}
        for node in self.nodeList:
            if node.epsFlag == 1:
                for ep, ep_nodes in epList.items():
                    if node.nodeID in ep_nodes:
                        if node.nodeID not in eps_ep:
                            eps_ep[node.nodeID] = []  # 初始化键的值为列表
                        eps_ep[node.nodeID].append(ep)  # 向列表中添加ep
                    
                        
        return eps_ep
    
    def get_eps_el_metrix(self, eps_ep, epList):
        remaining_num_changing = 2
        eps_el_metrix = {}
        eps_ep_node = {}
        for eps, ep_list in eps_ep.items():
            ep_list_node = []
            for ep_index in ep_list:
                ep_list_node.append(epList[ep_index])
            eps_ep_node[eps] = merge_lists(ep_list_node)
            print(eps, eps_ep_node[eps])
            eps_el_metrix[eps] = np.zeros((remaining_num_changing, len(self.nodeList)))

        return eps_el_metrix

def compare_and_retain_differences(A, B):
    # 检查矩阵A和B是否形状相同
    if A.shape == B.shape:
        # 创建一个新的矩阵C，初始值为0
        C = np.zeros_like(B)
        # 遍历矩阵A和B的每个元素，比较是否相同
        for i in range(A.shape[0]):
            for column_index in range(A.shape[1]):
                if A[i, column_index] != B[i, column_index]:
                    # print("两个矩阵不同")
                    C[i, column_index] = B[i, column_index]  # 如果不同，将B的对应元素保留
        
        # print("elMatrix:", A)
        # print("el_success:", B)
        return C  # 返回更新后的矩阵C
    # else:
    #     return None  # 如果形状不同，返回None表示无法比较
        
def get_eps_selectNode(M):
    eps_selectNode = {}
    for row in M:
        for index in range(M.shape[1]):
            if row[index] != 0:
                if (index+1) not in eps_selectNode:
                    eps_selectNode[index+1] = []
                eps_selectNode[index+1].append(row[index])
                # eps_selectNode[index+1].append(", ")
    return eps_selectNode


def sliding_matrix(input_matrix):
    result_matrix = np.copy(input_matrix)
    result_matrix[:-1] = input_matrix[1:]
    result_matrix[-1] = 0

    return result_matrix

# def update_node_select_mlp(node, Self):
#     if node.epsFlag == 1:
#         print(f"node{node.nodeID} is eps")
#         ec_counter = {}
#         if node.adjacentNodes:
#             excluded_values = Self.get_excluded_values(node.nodeID)
#             for neighbor in node.adjacentNodes:
#                 # Self.el_success_looping = copy.deepcopy(Self.el_success)
#                 el_success_looping_neighbor = copy.deepcopy(Self.el_success)

#                 if neighbor not in excluded_values:
#                     # Self.el_success_looping[self.remainingNumchanging-1][node.nodeID-1] = neighbor
#                     el_success_looping_neighbor[self.remainingNumchanging-1][node.nodeID-1] = neighbor
#                     ec_counter[neighbor] = Self.calculateEcCount_mlp(el_success_looping_neighbor)
#                     print(f"node {node.nodeID} with neighbor {neighbor} has payoff {ec_counter[neighbor]}")
#         if ec_counter:
#             node.selectNodeID = max(ec_counter, key = ec_counter.get)
#             print(f"max is {max(ec_counter, key = ec_counter.get)}")
#             print(f"node{node.nodeID} has selected neighbor {node.selectNodeID}")
#             Self.el_success[self.remainingNumchanging-1][node.nodeID-1] = node.selectNodeID

# 将矩阵转换为字符串
def matrix_to_str(matrix):
    return matrix.tostring()

# 将字符串转换为矩阵
def str_to_matrix(string, shape, dtype=int):
    return np.frombuffer(string, dtype=dtype).reshape(shape)

def matrix_to_tuple(matrix):
    """
    将矩阵转换为元组
    """
    return tuple(map(tuple, matrix))

def tuple_to_matrix(tup):
    """
    将元组还原成矩阵
    """
    return np.array(tup)

def merge_lists(lists):
    merged_set = set()
    # print(lists)
    for lst in lists:
        # print(lst)
        merged_set.update(lst)  # 使用update()将每个列表中的元素添加到集合中
        # print(merged_set)

    merged_list = list(merged_set)
    return merged_list

def reorder_array(a, b):
    # 根据a中元素顺序重新排序b数组中元素
    b_sorted = [x for x in a if x in b]
    return b_sorted